package com.qrpcw.algorithms;
import java.util.Arrays;
import java.util.Random;

public class InsertionSort {

	public static void main(String[] args) {
		InsertionSort sort = new InsertionSort();
		int[] rad = sort.generateRandomNumbers(10);
		System.out.println(Arrays.toString(rad));
		System.out.println(Arrays.toString(sort.insertionSort(rad)));
	}
	
	public int[] insertionSort(int[] a){
		int i,j;
		int key;
		for (i=1; i<a.length; i++){
			key = a[i];
			j = i - 1;
			while(j>=0 && a[j]>key){
				a[j+1] = a[j]; 
				j--; //always keep one before key
				a[j+1] = key; //i+1 is key
			}
		}
		return a;
	}
	
	private int[] generateRandomNumbers(int n){
		int[] result = new int[n];	    
		Random random = new Random();	    
		for (int i = 0; i < result.length; i++){		    
			result[i] = random.nextInt(n * 10);	    
		}	    
		return result;	
	}
}
